package gold.digger;

import gold.utils.InputUtil;
import lombok.val;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC675 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        private int[][] directions = {
                {0, 1},
                {0, -1},
                {1, 0},
                {-1, 0}};

        public int cutOffTree(List<List<Integer>> forest) {
            if (forest.get(0).get(0) == 0) return -1;
            int m = forest.size(), n = forest.get(0).size();
            Map<Integer, int[]> destMap = new TreeMap<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
//                    if (i == 0 && j == 0) continue;     此处需要注意，0，0虽然是出发点，但也可能出现在destmap中，并且可能不是
// 第一个，可能出现在中间，重复访问0，0，因此此处不可以加上特殊处理，将其从destmap中移除
                    if (forest.get(i).get(j) > 1) destMap.put(forest.get(i).get(j), new int[]{i, j});
                }
            }

            int[] pre = new int[]{0, 0};
            int totalStep = 0;
            for (int[] point : destMap.values()) {
                int curPathStep = findPathByBFS(forest, pre[0], pre[1], point[0], point[1]);
                if (curPathStep < 0) return -1;
                totalStep += curPathStep;
                pre = point;
            }

            return totalStep;
        }

        public int findPathByBFS(List<List<Integer>> forest, int startX, int startY, int endX, int endY) {
            int pathStep = 0;
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{startX, startY});
            int nextX, nextY;
            boolean[][] visited = new boolean[forest.size()][forest.get(0).size()];
            visited[startX][startY] = true;

            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[] cur = queue.poll();

                    if (cur[0] == endX && cur[1] == endY) return pathStep;

                    for (int[] direction : directions) {
                        nextX = cur[0] + direction[0];
                        nextY = cur[1] + direction[1];
                        if (nextX < 0 || nextX >= forest.size() || nextY < 0 ||
                                nextY >= forest.get(0).size() || visited[nextX][nextY] || forest.get(nextX).get(nextY) <= 0)
                            continue;
                        queue.offer(new int[]{nextX, nextY});
                        visited[nextX][nextY] = true;
                    }
                }
                ++pathStep;
            }

            return -1;
        }

        public int cutOffTree_standard_answer(List<List<Integer>> forest) {
            List<int[]> trees = new ArrayList();
            for (int r = 0; r < forest.size(); ++r) {
                for (int c = 0; c < forest.get(0).size(); ++c) {
                    int v = forest.get(r).get(c);
                    if (v > 1) trees.add(new int[]{v, r, c});
                }
            }

            Collections.sort(trees, (a, b) -> Integer.compare(a[0], b[0]));

            int ans = 0, sr = 0, sc = 0;
            for (int[] tree : trees) {
                int d = bfs(forest, sr, sc, tree[1], tree[2]);
                if (d < 0) return -1;
                ans += d;
                sr = tree[1];
                sc = tree[2];
            }
            return ans;
        }

        public int bfs(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {
            int R = forest.size(), C = forest.get(0).size();
            Queue<int[]> queue = new LinkedList();
            queue.add(new int[]{sr, sc, 0});
            boolean[][] seen = new boolean[R][C];
            seen[sr][sc] = true;
            while (!queue.isEmpty()) {
                int[] cur = queue.poll();
                if (cur[0] == tr && cur[1] == tc) return cur[2];

                for (int[] direction : directions) {
                    int r = cur[0] + direction[0];
                    int c = cur[1] + direction[1];
                    if (0 <= r && r < R && 0 <= c && c < C &&
                            !seen[r][c] && forest.get(r).get(c) > 0) {
                        seen[r][c] = true;
                        queue.add(new int[]{r, c, cur[2] + 1});
                    }
                }
            }
            return -1;
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> forest = InputUtil.toDoubleIntegerList("[[54581641,64080174,24346381,69107959],[86374198,61363882,68783324,79706116],[668150,92178815,89819108,94701471],[83920491,22724204,46281641,47531096],[89078499,18904913,25462145,60813308]]");

        System.out.println(solution.cutOffTree(forest));
    }

    public static void main(String[] args) throws Exception {
        LC675 an = new LC675();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
